package array.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName DeleteDup
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-02 16:56
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class DeleteDup {


    /**
     * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
     * <p>
     * 在 S 上反复执行重复项删除操作，直到无法继续删除。
     * <p>
     * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     * <p>
     * 示例：
     * <p>
     * 输入："abbaca"
     * 输出："ca"
     * 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
     * 提示：
     * <p>
     * 1 <= S.length <= 20000
     * S 仅由小写英文字母组成。
     */
    public String removeDuplicates(String s) {

        if (s.length() == 0 || s.length() == 1) {
            return s;
        }

        Stack<Character> stack = new Stack<>();

        char[] newArray = s.toCharArray();
        stack.push(newArray[0]);
        for (int i = 1; i < newArray.length; i++) {
            if (stack.isEmpty()) {
                stack.push(newArray[i]);
                continue;
            }
            Character pop = stack.peek();
            if (pop != newArray[i]) {
                stack.push(newArray[i]);
            } else {
                stack.pop();
            }
        }
        List<Character> characterList = new ArrayList<>();

        if (stack.isEmpty()) {
            return "";
        }
        while (!stack.isEmpty()) {
            characterList.add(stack.pop());
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = characterList.size() - 1; i >= 0; i--) {
            stringBuilder.append(characterList.get(i));
        }
        return stringBuilder.toString();
    }


    public String removeDuplicates1(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.isEmpty() || stack.peek() != c) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        String str = "";
        while (!stack.isEmpty()) {
            str = stack.pop() + str;
        }
        return str;
    }

    public static void main(String[] args) {
        String s = "abbaca";
        DeleteDup deleteDup = new DeleteDup();
        String s1 = deleteDup.removeDuplicates1(s);
        System.out.println(s1);
    }
}